C1 Bresenham's line drawing

2026/1/13 · Tech

V1 朴素插值法算法

/**
 * @brief 朴素参数插值法画线
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param framebuffer 
 * @param color 
 */
void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) {
    for (float t=0.; t<1.; t+=.02) {
        int x = std::round( ax + (bx-ax)*t );
        int y = std::round( ay + (by-ay)*t );
        framebuffer.set(x, y, color);
    }
}

当 $t = 0$ 时，点在起点；当 $t = 1$ 时，点在终点；
代码硬编码步长为0.02，说明固定采样50/51个点。

缺点：

长线会有“断点”，变成虚线形式。
短线会导致过于密集。
浮点数运算浪费性能。

V1.1 改进：采取不同的采样策略

/**
 * @brief 朴素参数插值法画线：步长改进
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param framebuffer 
 * @param color 
 */
void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) {
    if(ax > bx) {   // ltr
        std::swap(ax, bx);
        std::swap(ay, by);
    }
    for(int x = ax; x <= bx; x ++) {
        float t = (x - ax) / static_cast<float>(bx - ax);
        int y = std::round(ay + (by - ay) * t);
        framebuffer.set(x, y, color);
    }
}

改进：
- 不再固定步长，可以比较合理的取样
缺陷：
- 不适用于陡峭的线，会导致线的断裂甚至程序崩溃（除以0）

V1.2 改进：识别陡峭部分

/**
 * @brief 朴素参数插值法画线：步长改进 + 陡峭翻转
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param framebuffer 
 * @param color 
 */
void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) {
    bool isSteep = std::abs(ax - bx) < std::abs(ay - by);
    if(isSteep) {
        std::swap(ax, ay);
        std::swap(bx, by);
    }
    if(ax > bx) {   // ltr
        std::swap(ax, bx);
        std::swap(ay, by);
    }
    for(int x = ax; x <= bx; x ++) {
        float t = (x - ax) / static_cast<float>(bx - ax);
        int y = std::round(ay + (by - ay) * t);
        isSteep ? framebuffer.set(y, x, color) : framebuffer.set(x, y, color);
    }
}

优点

解决了之前的所有痛点
缺陷
性能瓶颈：循环体内部包含除法 / 浮点乘法 / 浮点加法 / 取整函数

V2 DDA 算法

DDA：digital differential analyzer
基于直线的微分方程来生成直线的方法

直线斜率：
$m = \frac{y2-y1}{x2-x1} = \frac{dy}{dx}$

通过 V1.2 的式子，可以看出

初始时， $x_0 = ax$ ， $y_0 = ay$ ，还未开始循环步进/采样

$x_1 = ax + 1，y_1 = y_0 + \frac{dy}{dx}$
$x_2 = ax + 2，y_2 = y_1 + \frac{dy}{dx}$
$x_3 = ax + 3，y_3 = y_2 + \frac{dy}{dx}$
$\dots$

观察 $y$ 的序列，可以将 $v1.2$ 优化为如下算法：

/**
 * @brief DDA法
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param framebuffer 
 * @param color 
 */
void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) {
    bool isSteep = std::abs(ax - bx) < std::abs(ay - by);
    if(isSteep) {
        std::swap(ax, ay);
        std::swap(bx, by);
    }
    if(ax > bx) {   // ltr
        std::swap(ax, bx);
        std::swap(ay, by);
    }
    float y = ay;
    for(int x = ax; x <= bx; x ++) {
        isSteep ? framebuffer.set(y, x, color) : framebuffer.set(x, y, color);
        y += (by - ay) / static_cast<float>(bx - ax);   // 每次x进，y就增斜率量
    }
}

效果如下：

优点

易理解
速度快
化除为加

缺陷

目前每轮循环还是包含除法（编译器可以优化）
没有解决浮点数计算的问题，对硬件不友好（还引入了float y )

V3 Bresenham 算法

前面所做的积累

依照直线调整步长，而非固定步长
只做平缓直线的绘制（陡峭情形化归到平缓）
循环除法 $\to$ 累加法

注意第2点，我们总是做平缓情形，这说明直线的斜率有
$|k| \leq 1$
这说明在主循环中，我们每当对 $x$ 做累加操作时， $y$ 的增量总不会超过 $1$ .

由于我们要求的 $x, y$ 坐标皆为整数，所以没有必要在 $x$ 累加时，通过直线方程去计算 $y$ 的坐标（因为这个结果通常是浮点数），我们引入一个 $e$ 来记录每一像素点与目标直线的误差（ $y$ 值）。

每当x的值增加1，误差的值就会增加斜率的值 $\frac{dx}{dy}$
每当误差的值超出0.5，线就会比较靠近下一个点，因此y的值便会加1，且误差减1。

代码如下：

/**
 * @brief Bresenham法
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param framebuffer 
 * @param color 
 */
void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) {
    bool steep = std::abs(ax-bx) < std::abs(ay-by);
    if (steep) { // if the line is steep, we transpose the image
        std::swap(ax, ay);
        std::swap(bx, by);
    }
    if (ax>bx) { // make it left−to−right
        std::swap(ax, bx);
        std::swap(ay, by);
    }
    int y = ay;
    float error = 0;
    for (int x=ax; x<=bx; x++) {
        if (steep) // if transposed, de−transpose
            framebuffer.set(y, x, color);
        else
            framebuffer.set(x, y, color);
        error += std::abs(by-ay)/static_cast<float>(bx-ax);
        if (error>.5) {
            y += by > ay ? 1 : -1;
            error -= 1.;
        }
    }
}

上述是算法原理可理解性的代码，实际上可以去除浮点数，得到整数形式的算法，代码如下：

浮点数形式
- 判定 $error \gt 0.5$
- 每轮循环 $error$ += $\frac{dy}{dx}$
- 更新 $y$ 时， $error$ -= $1$
整数形式
- 判定 $ierror \gt dy$
- 每轮循环 $ierror$ += $2dy$
- 更新 $y$ 时， $ierror$ -= $2dx$

/**
 * @brief Bresenham法
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param framebuffer 
 * @param color 
 */
void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) {
    bool isSteep = std::abs(ax - bx) < std::abs(ay - by);
    if(isSteep) {
        std::swap(ax, ay);
        std::swap(bx, by);
    }
    if(ax > bx) {   // ltr
        std::swap(ax, bx);
        std::swap(ay, by);
    }
    int y = ay;
    int ierror = 0;
    for(int x = ax; x <= bx; x ++) {
        isSteep ? framebuffer.set(y, x, color) : framebuffer.set(x, y, color);
        ierror += 2 * std::abs(by - ay);
        if(ierror > bx - ax) {
            y += by > ay ? 1 : -1;
            ierror -= 2 * (bx - ax);
        }
    }
}

这是我们最终使用的画线算法。效果如下：